#include "atlas.h"

static inline rect_t rect_create(uint16_t x, uint16_t y, uint16_t w, uint16_t h)
{
	return (rect_t){x, y, w, h};
}

static inline bool rect_lower(const rect_t &r1, const rect_t &r2)
{
	return r1.w < r2.w || r1.h < r2.h;
}

static inline bool rect_fit(const rect_t &r1, const rect_t &r2)
{
	return r1.w == r2.w && r1.h == r2.h;
}

static node_t* atlas_node_create(const rect_t &rect)
{
	node_t *node = (node_t *)malloc(sizeof(node_t));
	
	node->left   = NULL;
	node->right  = NULL;
	node->bitmap = NULL;
	node->rect   = rect;
	
	return node;
}

static node_t* atlas_node_insert(node_t *node, uint16_t width, uint16_t height)
{
	if (node->left && node->right)
	{
		node_t *new_node = atlas_node_insert(node->left, width, height);
		
		if (new_node == NULL)
			new_node = atlas_node_insert(node->right, width, height);
		
		return new_node;
	} else
	{
		if (node->bitmap)
			return NULL;
		
		if (rect_lower(node->rect, rect_create(0, 0, width, height)))
			return NULL;
		
		if (rect_fit(node->rect, rect_create(0, 0, width, height)))
			return node;
		
		uint16_t dw = node->rect.w - width;
		uint16_t dh = node->rect.h - height;
		
		rect_t r1, r2;
		
		if (dw > dh)
		{
			r1 = rect_create(node->rect.x, node->rect.y, width, node->rect.h);
			r2 = rect_create(node->rect.x + width, node->rect.y, node->rect.w - width, node->rect.h);
		} else
		{
			r1 = rect_create(node->rect.x, node->rect.y, node->rect.w, height);
			r2 = rect_create(node->rect.x, node->rect.y + height, node->rect.w, node->rect.h - height);
		}
		
		node->left  = atlas_node_create(r1);
		node->right = atlas_node_create(r2);
		
		return atlas_node_insert(node->left, width, height);
	}
}

atlas_t* atlas_create(uint16_t width, uint16_t height)
{
	atlas_t *atlas = (atlas_t *)malloc(sizeof(atlas_t));
	
	atlas->root = atlas_node_create(rect_create(0, 0, width, height));
	
	return atlas;
}

void atlas_destroy(atlas_t *atlas)
{
	// do nothing
}

node_t* atlas_insert(atlas_t *atlas, bitmap_t *bitmap)
{
	node_t *node = atlas_node_insert(atlas->root, bitmap->w, bitmap->h);
	
	if (node)
		node->bitmap = bitmap;
	
	return node;
}

static void atlas_node_assemble(const node_t *node, uint16_t width, uint16_t *bitmap)
{
	if (node->left)
		atlas_node_assemble(node->left, width, bitmap);
	
	if (node->right)
		atlas_node_assemble(node->right, width, bitmap);
	
	bitmap_t *bmp = node->bitmap;
	
	if (bmp == NULL || bmp->w == 0 || bmp->h == 0)
		return;
	
	for (int j = 0; j < bmp->h; ++j)
		memcpy(bitmap + node->rect.x + (j + node->rect.y) * width, bmp->data + j * bmp->w, bmp->w * 2);
}

void atlas_assemble(const atlas_t *atlas, uint16_t *bitmap, uint16_t width, uint16_t height)
{
	if (atlas == NULL || atlas->root == NULL)
		return;
	
	if (atlas->root->rect.w > width || atlas->root->rect.h > height)
		return;
	
	memset(bitmap, 0, width * height * 2);
	
	atlas_node_assemble(atlas->root, width, bitmap);
}
